from datastruct import ListNode, TreeNode
from typing import Optional


def hasCycle(head: Optional[ListNode]) -> bool:
    if head is None or head.next is None:
        return False
    slow = head
    fast = head.next
    if fast is not None:
        fast = fast.next
    while fast is not None and fast != slow:
        slow = slow.next
        fast = fast.next
        if fast is not None:
            fast = fast.next
    return fast == slow


def maxDepth(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0
    else:
        return 1 + max(maxDepth(root.left), maxDepth(root.right))


def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if (p is None and q is not None) or (p is not None and q is None):
        return False
    elif p is None and q is None:
        return True
    else:
        if p.val != q.val:
            return False
        else:
            return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)


def mergeTwoLists(list1: Optional[ListNode],
                  list2: Optional[ListNode]) -> Optional[ListNode]:
    if list1 is not None and list2 is None:
        return list1
    elif list1 is None and list2 is not None:
        return list2
    elif list1 is None and list2 is None:
        return list2
    else:
        if list1.val <= list2.val:
            list1.next = mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = mergeTwoLists(list1, list2.next)
            return list2


def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
    else:
        l = invertTree(root.left)
        r = invertTree(root.right)
        root.left = r
        root.right = l
        return root


def isSymmetricTree(root1: Optional[TreeNode],
                    root2: Optional[TreeNode]) -> bool:
    if root1 is None and root2 is None:
        return True
    elif (root1 is None and root2 is not None) or (root1 is not None
                                                   and root2 is None):
        return False
    else:
        if root1.val != root2.val:
            return False
        else:
            return isSymmetricTree(root1.left,
                                   root2.right) and isSymmetricTree(
                                       root1.right, root2.left)


def isSymmetric(root: Optional[TreeNode]) -> bool:
    return isSymmetricTree(root, root)


def hasPathSum(root: Optional[TreeNode], targetSum: int):
    if root is None:
        return False
    else:
        if root.left is None and root.right is None and targetSum == root.val:
            return True
        elif root is not None and root.left is None and root.right is None and targetSum != root.val:
            return False
        else:
            return hasPathSum(root.left, targetSum - root.val) or hasPathSum(
                root.right, targetSum - root.val)
